using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;

namespace Dida
{
	public class SortedSet<T> : ISet<T>, ICloneable
	{
		static Comparer defComparer = new Comparer(CultureInfo.InvariantCulture);

		IComparer comparer;

		Node root;
		int count = 0;

		public SortedSet()
		{
			comparer = defComparer;
		}

		public SortedSet(IComparer comparer)
		{
			this.comparer = comparer;
		}

		public SortedSet(IEnumerable<T> src, bool sorted, IComparer comparer)
		{
			this.comparer = comparer;

			IList<T> srcList;

			if (!sorted)
			{
				List<T> sortedList = new List<T>(src);
				sortedList.Sort(
					delegate(T a, T b)
					{
						return comparer.Compare(a, b);
					});
				srcList = sortedList;
			}
			else if (src is IList<T>)
				srcList = (IList<T>)src;
			else
				srcList = new List<T>(src);

			if (srcList.Count == 0)
			{
				root = null;
				return;
			}

			root = new Node(srcList, 0, srcList.Count, null,
				this, Node.CalcBalancedDepth(srcList.Count));
			count = srcList.Count;
		}

		public SortedSet(IEnumerable<T> src, bool sorted, IComparer<T> comparer)
			: this(src,sorted,defComparer)
		{
		}

		public SortedSet(IEnumerable<T> src, bool sorted)
			: this(src, sorted, defComparer)
		{
		}

		public SortedSet(IEnumerable<T> src)
			: this(src, false, defComparer)
		{
		}

		public bool IsReadOnly
		{
			get { return false; }
		}

		/// <summary>
		/// Adds the given value to this set. If a similar item already exists,
		/// the item won't be added.
		/// </summary>
		/// <param name="value">The value to insert.</param>
		/// <returns>true if the item was successfully added, 
		/// false if a similar value already exists in this set.</returns>
		public bool Add(T value)
		{
			if (root != null)
			{
				Node newNode = new Node(value, this);
				bool res = root.Insert(newNode);
				if (res)
					count++;
				return res;
			}
			else
			{
				root = new Node(value, this);
				root.leftChild = new Node(null, this);
				root.leftChild.parentNode = root;
				root.rightChild = new Node(null, this);
				root.rightChild.parentNode = root;

				count++;
				return true;
			}
		}

		void ICollection<T>.Add(T value)
		{
			Add(value);
		}

		public bool Remove(T value)
		{
			Node node = root.Find(value);
			if (node != null)
			{
				if (node.leftChild.value == null || node.rightChild.value == null)
					node.DeleteOneChild();
				else
				{
					Node nodeToDelete = node.leftChild.MaxInSubtree;
					node.value = nodeToDelete.value;
					node.DeleteOneChild();
				}

				count--;
				return true;
			}
			else
				return false;
		}

		public void Clear()
		{
			root = null;
			count = 0;
		}

		public bool Contains(T value)
		{
			if (root != null)
				return root.Contains(value);
			else
				return false;
		}

		public T GetAnyValue()
		{
			return (T)root.value;
		}

		public void CopyTo(T[] dest, int writePtr)
		{
			if (root != null)
				root.CopyToArray(dest, ref writePtr);
		}

		/// <summary>
		/// Returns an array that contains all items in this set.
		/// This array is guaranteed to be sorted.
		/// </summary>
		/// <returns>The array containing the items of this set.</returns>
		public T[] ToArray()
		{
			if (root != null)
			{
				T[] ret = new T[count];
				int writePtr = 0;
				root.CopyToArray(ret, ref writePtr);
				return ret;
			}
			else
				return new T[0];
		}

		/// <summary>
		/// Gets the elements of this set that are not part of set b.
		/// </summary>
		/// <param name="b">The set of values that should not be included
		/// in the result.</param>
		/// <returns>The set that contains all values that aren't psrt of b.</returns>
		public SortedSet<T> GetDifference(ISet<T> b)
		{
			if (b is SortedSet<T>)
			{
				SortedSet<T> bSortedSet = (SortedSet<T>)b;
				if (comparer == bSortedSet.comparer)
				{
					return GetDifferenceSortedSet((SortedSet<T>)b);
				}
			}
			
			List<T> flatList = new List<T>();
			foreach(T cur in this)
				if(!b.Contains(cur))
					flatList.Add(cur);

			return new SortedSet<T>(flatList, true, comparer);
		}

		private SortedSet<T> GetDifferenceSortedSet(SortedSet<T> b)
		{
			Debug.Assert(comparer == b.comparer);

			if (count == 0)
				return new SortedSet<T>(comparer);
			if (b.count == 0)
				return Clone();

			List<T> tmpres = new List<T>();

			IEnumerator<T> aEnum = GetEnumerator();
			IEnumerator<T> bEnum = b.GetEnumerator();

			bool moveRes = aEnum.MoveNext();
			Debug.Assert(moveRes, "The first call to MoveNext on a's enumerator " +
				"should return true, since it's count field wasn't 0");

			moveRes = bEnum.MoveNext();
			Debug.Assert(moveRes, "The first call to MoveNext on b's enumerator " +
				"should return true, since it's count field wasn't 0");

			while (true)
			{
				int compareRes = comparer.Compare(aEnum.Current, bEnum.Current);
				if (compareRes == -1)
				{
					tmpres.Add(aEnum.Current);

					if (!aEnum.MoveNext())
						break;
				}
				else if (compareRes == 1)
				{
					if (!bEnum.MoveNext())
					{
						while (aEnum.MoveNext())
							tmpres.Add(aEnum.Current);
						break;
					}
				}
				else
				{
					if (!aEnum.MoveNext())
						break;

					if (!bEnum.MoveNext())
					{
						while (aEnum.MoveNext())
							tmpres.Add(aEnum.Current);
						break;
					}
				}
			}

			return new SortedSet<T>(tmpres, true, comparer);
		}

		ISet<T> ISet<T>.GetDifference(ISet<T> b)
		{
			return GetDifference(b);
		}

		public SortedSet<T> GetIntersection(ISet<T> b)
		{
			if (b is SortedSet<T>)
			{
				SortedSet<T> bSortedSet = (SortedSet<T>)b;
				if (comparer == bSortedSet.comparer)
				{
					return GetIntersectionSortedSets(bSortedSet);
				}
			}

			SortedSet<T> ret = new SortedSet<T>(comparer);
			ISet<T> big, small;
			if (((ICollection)b).Count > Count)
			{
				big = b;
				small = this;
			}
			else
			{
				big = this;
				small = b;
			}

			foreach (T cur in small)
			{
				if (big.Contains(cur))
					ret.Add(cur);
			}

			return ret;
		}

		private SortedSet<T> GetIntersectionSortedSets(SortedSet<T> b)
		{
			Debug.Assert(comparer == b.comparer);

			if (count == 0)
				return new SortedSet<T>(comparer);
			if (b.count == 0)
				return Clone();

			List<T> tmpres = new List<T>();

			IEnumerator<T> aEnum = GetEnumerator();
			IEnumerator<T> bEnum = b.GetEnumerator();

			bool moveRes = aEnum.MoveNext();
			Debug.Assert(moveRes, "The first call to MoveNext on a's enumerator " +
				"should return true, since it's count field wasn't 0");

			moveRes = bEnum.MoveNext();
			Debug.Assert(moveRes, "The first call to MoveNext on b's enumerator " +
				"should return true, since it's count field wasn't 0");

			while (true)
			{
				int compareRes = comparer.Compare(aEnum.Current, bEnum.Current);
				if (compareRes == -1)
				{
					if (!aEnum.MoveNext())
						break;
				}
				else if (compareRes == 1)
				{
					if (!bEnum.MoveNext())
					{
						while (aEnum.MoveNext())
							tmpres.Add(aEnum.Current);
						break;
					}
				}
				else
				{
					tmpres.Add(aEnum.Current);

					if (!aEnum.MoveNext())
						break;

					if (!bEnum.MoveNext())
					{
						while (aEnum.MoveNext())
							;
						break;
					}
				}
			}

			return new SortedSet<T>(tmpres, true, comparer);
		}

		public SortedSet<T> Clone()
		{
			SortedSet<T> ret = new SortedSet<T>();
			ret.comparer = comparer;
			ret.count = count;
			if (root != null)
				ret.root = root.Clone(ret);
			return ret;
		}

		public IEnumerator<T> GetEnumerator()
		{
			return new Enumerator(this);
		}

		IEnumerator IEnumerable.GetEnumerator()
		{
			return new Enumerator(this);
		}

		#region Debugging code

		public void ValidateTree()
		{
			if (root != null)
			{
				Debug.Assert(!root.isRed, "The root should not be red");

				Dictionary<Node, object> checkedNodes = new Dictionary<Node, object>();
				root.ValidateParentChildRelations(checkedNodes);

				root.ValidateTree(false);
				root.ValidateBlackNodeCount();
			}
		}

		public void ValidateIteratingOrder()
		{
			T prev = default(T);
			bool hasPrev = false;
			foreach (T t in this)
			{
				if (hasPrev)
				{
					Debug.Assert(comparer.Compare(prev, t) == -1);
					prev = t;
				}
				else
				{
					prev = t;
					hasPrev = true;
				}
			}
		}

		#endregion

		#region ICollection Members

		public void CopyTo(Array array, int index)
		{
			if (root != null)
			{
				root.CopyToArray(array, ref index);
			}
		}

		public int Count
		{
			get { return count; }
		}

		public bool IsSynchronized
		{
			get { return false; }
		}

		public object SyncRoot
		{
			get { return this; }
		}

		#endregion

		#region ICloneable Members

		object ICloneable.Clone()
		{
			return Clone();
		}

		#endregion

		private class Node
		{
			public object value;

			public SortedSet<T> parentSet;
			public Node parentNode;

			public Node leftChild = null;
			public Node rightChild = null;
			public bool isRed = false;

			public Node(object value,SortedSet<T> parentSet)
			{
				this.value = value;
				this.parentSet = parentSet;
			}

			/// <summary>
			/// Constructs a (sub)tree from a sorted array.
			/// </summary>
			/// <param name="src">The array</param>
			/// <param name="first">The first item to use</param>
			/// <param name="last">The last item + 1 to use (so each item's index
			/// is first &lt;= index &lt; last</param>
			/// <param name="parentNode">The parent node, or null if it's
			/// the root node</param>
			/// <param name="parentSet">The set this node belongs to.</param>
			/// <param name="balancedDepth">The depth at which all nodes will be
			/// coloured red.</param>
			public Node(IList<T> src,int first,int last,Node parentNode,
				SortedSet<T> parentSet,int balancedDepth)
			{
				this.parentNode = parentNode;
				this.parentSet = parentSet;
				this.isRed = balancedDepth == 0;

				int n = last - first;
				int nOnLeft = (n - 1) / 2;
				int nOnRight = (n - 1) - nOnLeft;

				value = src[first + nOnLeft];

				if (nOnLeft != 0)
				{
					leftChild = new Node(src, first, first + nOnLeft,
						this,parentSet,balancedDepth - 1);
				}
				else
				{
					leftChild = new Node(null, parentSet);
					leftChild.parentNode = this;
				}

				if (nOnRight != 0)
				{
					rightChild = new Node(src, last - nOnRight, 
					last,this,parentSet,balancedDepth - 1);
				}
				else
				{
					rightChild = new Node(null, parentSet);
					rightChild.parentNode = this;
				}				
			}

			public static int CalcBalancedDepth(int totalNNodes)
			{
				int depth = 0;
				totalNNodes++;
				while (totalNNodes != 0)
				{
					totalNNodes >>= 1;
					if (totalNNodes == 0)
						break;
					depth++;
				}
				return depth;
			}

			public bool Insert(Node node)
			{
				int compareRes = parentSet.comparer.Compare(node.value, value);
				if (compareRes == -1)
				{
					if (leftChild.value != null)
						return leftChild.Insert(node);
					else
					{
						node.leftChild = leftChild;
						node.leftChild.parentNode = node;
						node.rightChild = new Node(null, parentSet);
						node.rightChild.parentNode = node;

						leftChild = node;
						node.isRed = true;
						node.parentNode = this;

						node.Rebalance();

						return true;
					}
				}
				else if (compareRes == 1)
				{
					if (rightChild.value != null)
						return rightChild.Insert(node);
					else
					{
						node.leftChild = rightChild;
						node.leftChild.parentNode = node;
						node.rightChild = new Node(null, parentSet);
						node.rightChild.parentNode = node;

						rightChild = node;
						node.parentNode = this;
						node.isRed = true;

						node.Rebalance();

						return true;
					}
				}
				else
				{
					// a similar item already exists.
					return false;
				}
			}

			public Node Uncle
			{
				get
				{
					Node grandPa = parentNode.parentNode;
					if (grandPa.leftChild == parentNode)
						return grandPa.rightChild;
					else
						return grandPa.leftChild;
				}
			}

			private void Rebalance()
			{
				if (parentNode == null)
				{
					isRed = false;
					return;
				}

				if (parentNode.isRed)
				{
					Node uncle = Uncle;
					if (uncle.isRed)
					{
						parentNode.isRed = false;
						uncle.isRed = false;

						Node grandPa = parentNode.parentNode;
						grandPa.isRed = true;
						grandPa.Rebalance();
					}
					else
					{
						bool isLeft = parentNode.leftChild == this;
						bool parentIsLeft = parentNode.parentNode.leftChild == parentNode;

						if (parentIsLeft)
						{
							if (!isLeft)
							{
								parentNode.RotateLeft();
								parentNode.RotateRight();

								isRed = false;
								rightChild.isRed = true;
							}
							else
							{
								parentNode.parentNode.RotateRight();

								parentNode.isRed = false;
								parentNode.rightChild.isRed = true;								
							}
						}
						else
						{
							if (isLeft)
							{
								parentNode.RotateRight();
								parentNode.RotateLeft();

								isRed = false;
								leftChild.isRed = true;								
							}
							else
							{
								parentNode.parentNode.RotateLeft();

								parentNode.isRed = false;
								parentNode.leftChild.isRed = true;								
							}
						}
					}
				}
			}

			private void RotateRight()
			{
				Node oldParent = parentNode;

				parentNode = leftChild;
				parentNode.parentNode = oldParent;
				if (oldParent != null)
				{
					if (this == oldParent.leftChild)
						oldParent.leftChild = parentNode;
					else
						oldParent.rightChild = parentNode;
				}
				else
					parentSet.root = parentNode;

				leftChild = parentNode.rightChild;
				leftChild.parentNode = this;
				parentNode.rightChild = this;
				parentNode.rightChild.parentNode = parentNode;
			}

			private void RotateLeft()
			{
				Node oldParent = parentNode;

				parentNode = rightChild;
				parentNode.parentNode = oldParent;
				if (oldParent != null)
				{
					if (this == oldParent.leftChild)
						oldParent.leftChild = parentNode;
					else
						oldParent.rightChild = parentNode;
				}
				else
					parentSet.root = parentNode;

				rightChild = parentNode.leftChild;
				rightChild.parentNode = this;
				parentNode.leftChild = this;
				parentNode.leftChild.parentNode = parentNode;
			}

			public bool Contains(T valueToTest)
			{
				switch(parentSet.comparer.Compare(valueToTest,value))
				{
					case -1:
						if (leftChild.value != null)
							return leftChild.Contains(valueToTest);
						else
							return false;

					case 0:
						return true;

					case 1:
						if (rightChild.value != null)
							return rightChild.Contains(valueToTest);
						else
							return false;
				}

				Debug.Fail("IComparer.Compare should return -1, 0 or 1");
				return false;
			}

			public Node Find(T valueToFind)
			{
				int compareRes = parentSet.comparer.Compare(valueToFind, value);
				switch (compareRes)
				{
					case -1:
						if (leftChild.value != null)
							return leftChild.Find(valueToFind);
						else
							return null;

					case 0:
						return this;

					case 1:
						if (rightChild.value != null)
							return rightChild.Find(valueToFind);
						else
							return null;

					default:
						Debug.Fail("Invalid compare res: " + compareRes.ToString());
						return null;
				}
			}

			public Node MaxInSubtree
			{
				get
				{
					Node ret = this;
					while (ret.rightChild.value != null)
						ret = ret.rightChild;
					return ret;
				}
			}

			public Node MinInSubtree
			{
				get
				{
					Node ret = this;
					while (ret.leftChild.value != null)
						ret = ret.leftChild;
					return ret;
				}
			}

			public void DeleteOneChild()
			{
				Node child = leftChild.value != null ? leftChild : rightChild;

				child.parentNode = parentNode;
				if (child == leftChild)
					child.rightChild = rightChild;
				else
					child.leftChild = leftChild;

				if (!isRed)
				{
					if (child.isRed)
						child.isRed = false;
					else
						child.DeleteCase1();
				}
			}

			private void DeleteCase1()
			{
				if (parentNode == null)
				{
					parentSet.root = this;
					return;
				}
				else
					DeleteCase2();
			}

			private void DeleteCase2()
			{
				Node sibling = this == parentNode.leftChild ? 
					parentNode.rightChild : parentNode.leftChild;
				
				if(sibling.isRed)
				{
					parentNode.isRed = true;
					sibling.isRed = false;

					if (this == parentNode.leftChild)
						parentNode.RotateLeft();
					else
						parentNode.RotateRight();
				}

				DeleteCase3();
			}

			private void DeleteCase3()
			{
				Node sibling = this == parentNode.leftChild ?
					parentNode.rightChild : parentNode.leftChild;

				if (!parentNode.isRed && !sibling.isRed &&
					!sibling.leftChild.isRed && sibling.rightChild.isRed)
	   			{
					sibling.isRed = true;
					parentNode.DeleteCase1();
				}
				else
					DeleteCase4();
			}

			private void DeleteCase4()
			{
				Node sibling = this == parentNode.leftChild ?
					parentNode.rightChild : parentNode.leftChild;

				if (parentNode.isRed && !sibling.isRed &&
					!sibling.leftChild.isRed && !sibling.rightChild.isRed)
				{
					sibling.isRed = true;
					parentNode.isRed = false;
				}
				else
					DeleteCase5();
			}

			private void DeleteCase5()
			{
				Node sibling = this == parentNode.leftChild ?
					parentNode.rightChild : parentNode.leftChild;

				if (this == parentNode.leftChild && !sibling.isRed && 
					sibling.leftChild.isRed && !sibling.rightChild.isRed)
				{
					sibling.isRed = true;
					sibling.leftChild.isRed = false;
					sibling.RotateRight();
				}
				else if(this == parentNode.rightChild && !sibling.isRed && 
					!sibling.leftChild.isRed && sibling.rightChild.isRed)
				{
					sibling.isRed = true;
					sibling.rightChild.isRed = false;
					sibling.RotateLeft();
				}
				
				DeleteCase6();
			}

			private void DeleteCase6()
			{
				Node sibling = this == parentNode.leftChild ?
					parentNode.rightChild : parentNode.leftChild;

				sibling.isRed = parentNode.isRed;
				parentNode.isRed = false;

				if (this == parentNode.leftChild)
				{
					sibling.rightChild.isRed = false;
					parentNode.RotateLeft();
				}
				else
				{
					sibling.leftChild.isRed = false;
					parentNode.RotateRight();
				}
			}

			public Node FirstDescend
			{
				get
				{
					if(leftChild.value == null)
						return this;
					else
						return leftChild.FirstDescend;
				}
			}

			public Node NextNode
			{
				get
				{
					if (rightChild.value != null)
					{
						Node ret = rightChild;
						while (ret.leftChild.value != null)
							ret = ret.leftChild;
						return ret;
					}
					else
					{
						Node n = this;
						if (n.parentNode == null)
							return null;
						while (n == n.parentNode.rightChild) 
						{
							n = n.parentNode;
							if (n.parentNode == null)
								return null;
						}
						return n.parentNode;
					}
				}
			}

			public void CopyToArray(Array dest, ref int writePtr)
			{
				if (leftChild.value != null)
				{
					leftChild.CopyToArray(dest, ref writePtr);
				}

				dest.SetValue(value, writePtr);
				writePtr++;

				if (rightChild.value != null)
				{
					rightChild.CopyToArray(dest, ref writePtr);
				}
			}

			public Node Clone(SortedSet<T> parentSet)
			{
				Node ret = new Node(value, parentSet);
				ret.isRed = isRed;

				if (value != null)
				{
					ret.leftChild = leftChild.Clone(parentSet);
					ret.leftChild.parentNode = ret;
					ret.rightChild = rightChild.Clone(parentSet);
					ret.rightChild.parentNode = ret;
				}

				return ret;
			}

			#region Debugging code

			public void ValidateParentChildRelations(Dictionary<Node, object> checkedNodes)
			{
				Debug.Assert(!checkedNodes.ContainsKey(this),
					"Circular reference found in the tree");
				checkedNodes.Add(this, null);

				if (leftChild != null)
				{
					Debug.Assert(leftChild.parentNode == this);
					leftChild.ValidateParentChildRelations(checkedNodes);
				}

				if (rightChild != null)
				{
					Debug.Assert(rightChild.parentNode == this);
					rightChild.ValidateParentChildRelations(checkedNodes);
				}
			}

			public void ValidateTree(bool parentRed)
			{
				if (parentRed)
					Debug.Assert(!isRed,"The child nodes of a red node should be black.");
				if (leftChild.value != null)
				{
					Debug.Assert(parentSet.comparer.Compare(
						leftChild.value, value) == -1,"The left child of a node " + 
						"must have a lower value than the value of that node itself");
					leftChild.ValidateTree(isRed);
				}
				if (rightChild.value != null)
				{
					Debug.Assert(parentSet.comparer.Compare(
						rightChild.value, value) == 1, "The right child of a node " +
						"must have a higher value than the value of that node itself");
					rightChild.ValidateTree(isRed);
				}
			}

			public int ValidateBlackNodeCount()
			{
				int nBlackOnLeft = 0,nBlackOnRight = 0;
				if (leftChild != null)
					nBlackOnLeft = leftChild.ValidateBlackNodeCount();
				if (rightChild != null)
					nBlackOnRight = rightChild.ValidateBlackNodeCount();
				Debug.Assert(nBlackOnLeft == nBlackOnRight,
					"The number of black nodes should be equal on " + 
					"every possible path of the tree");

				if (isRed)
					return nBlackOnLeft;
				else
					return nBlackOnLeft + 1;
			}

			#endregion
		}

		private Node FirstNode
		{
			get
			{
				if (root != null)
					return root.FirstDescend;
				else
					return null;
			}
		}

		/// <summary>
		/// Gets the first item in this set. This is the item, that has
		/// the first position according to the sorting.
		/// </summary>
		public T First
		{
			get
			{
				return (T)FirstNode.value;
			}
		}

		private class Enumerator : IEnumerator<T>
		{
			private Node curNode = null;
			private SortedSet<T> set;

			public Enumerator(SortedSet<T> set)
			{
				this.set = set;
			}

			public T Current
			{
				get
				{ 
					return (T)curNode.value;
				}
			}

			object IEnumerator.Current
			{
				get
				{
					return curNode.value;
				}
			}

			public bool MoveNext()
			{
				if(curNode != null)
					curNode = curNode.NextNode;
				else
					curNode = set.FirstNode;

				return curNode != null;
			}

			public void Reset()
			{
				curNode = null;
			}

			public void Dispose() { }
		}		
	}
}